//给定一个已排序的正整数数组 nums，和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中，使得 [1, n] 区间内的任何数字都
//可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。 
//
// 示例 1: 
//
// 输入: nums = [1,3], n = 6
//输出: 1 
//解释:
//根据 nums 里现有的组合 [1], [3], [1,3]，可以得出 1, 3, 4。
//现在如果我们将 2 添加到 nums 中， 组合变为: [1], [2], [3], [1,3], [2,3], [1,2,3]。
//其和可以表示数字 1, 2, 3, 4, 5, 6，能够覆盖 [1, 6] 区间里所有的数。
//所以我们最少需要添加一个数字。 
//
// 示例 2: 
//
// 输入: nums = [1,5,10], n = 20
//输出: 2
//解释: 我们需要添加 [2, 4]。
// 
//
// 示例 3: 
//
// 输入: nums = [1,2,2], n = 5
//输出: 0
// 
// Related Topics 贪心 数组 
// 👍 283 👎 0

package leetcode.editor.cn;

/**
 * Java：按要求补齐数组
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P330_PatchingArray {
    public static void main(String[] args) {
        Solution solution = new P330_PatchingArray().new Solution();
        // TODO 此处开始你的表演

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minPatches(int[] nums, int n) {
            if (nums == null || nums.length == 0 || n <= 0) {
                return -1;
            }
            // 次数
            int patch = 0;
            // 当前最长的路径，防溢出要定义成long类型
            long range = 0;
            // 如果nums没有排序则此处需要排序
            for (int i = 0; i < nums.length; i++) {
                while (range + 1 < nums[i]) {
                    range += range + 1;
                    patch++;
                    if (range >= n) {
                        return patch;
                    }
                }
                // 到此处 1-(nums[i]-1)的路径已经搞定了
                range += nums[i];
                if (range >= n) {
                    return patch;
                }
            }
            // 跳出循环还是没搞定n，需要继续延申
            while (range + 1 < n) {
                range += range + 1;
                patch++;
            }
            return patch;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}